package demo.hw;

/**
 * 给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数，
 * 输入描述
 * 第一行输入两个正整数N，M，表示矩阵大小。
 * 接下来N行M列表示矩阵内容。下一行包含一个正整数K。下一行包含K个整数，表示所需包含的数组，K整数可能存在重复数字。
 * 所有输入数据小于1000。
 * 输出描述
 * 输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1
 * <p>
 * 示例1
 * 输入
 * 2 5
 * 1 2 2 3 1
 * 2 3 2 3 2
 * 3
 * 1 2 3
 * 输出
 * 2
 * 说明
 * 矩阵第0、1列包含了1、2、3，矩阵第3、4列包含了1、2、3
 * <p>
 * 示例2
 * 输入
 * 25
 * 12231
 * 13234
 * 3
 * 114
 * 输出
 * 5
 * 说明
 * 矩阵第1,2,3,4,5列包含了1,1,4
 */
public class _宽度最小的子矩阵 {
    public static void main(String[] args) {
        /*
         * 先统计k中每个数字出现次数need
         * 统计k中总共有几个数字needKinds
         * 遍历每列
         *  // 右扩把每行加起来
         *  遍历每行 如果命中v数字+1 ==need[v] 则次数needKinds--
         *
         * 当needKinds==0时左缩 去掉每列
         *  获取最小宽度
         *  当命中v数字次数==need[v]时needKinds++
         *  left++
         */
        int[][] mat = {
                {1, 2, 2, 3, 1},
                {1, 3, 2, 3, 4}
        };
        int[] k = {1, 1, 4};

        int N = mat.length;//行
        int M = mat[0].length;// 列

        int[] need = new int[1001];
        for (int i : k) {
            need[i]++;
        }
        int needKinds = 0; // 去重后数字总数 只在新种类第一次出现时才加needKinds
        for (int i = 0; i < 1001; i++) {
            if (need[i] != 0) {
                needKinds++;
            }
        }
        // 跨行、跨列的实时计数器
        int[] total = new int[1001]; // 滑动窗口中当前数字v的总数

        int minW = M + 1;

        // N行M列
        for (int left = 0, right = 0; right < M; right++) {
            // 右扩 把right右边列所有行加进来
            for (int r = 0; r < N; r++) {
                int v = mat[r][right];
                int old = total[v]++;
                if (old + 1 == need[v]) { // 数字v总数首次达标
                    needKinds--;
                }
            }
            // 左缩 只要满足条件就左缩
            while (needKinds == 0) {
                minW = Math.min(minW, right - left + 1);
                // 把left左边列所有行去掉
                for (int r = 0; r < N; r++) {
                    int v = mat[r][left];
                    int old = total[v]--;
                    if (old == need[v]) {
                        needKinds++;
                    }
                }
                left++;
            }
        }
        System.out.println(minW > M ? -1 : minW);
    }
}
